package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202408;

import java.util.HashMap;
import java.util.Map;

public class leetcode20240827 {
    public int medianOfUniquenessArray(int[] nums){
        int n=nums.length;
        long k=((long) n*(n+1)/2+1)/2;
        int left=0;
        int right=n;
        while(left+1<right){
            int mid=(left+right)/2;
            if(check(nums,mid,k)){
                right=mid;
            }else{
                left=mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums,int upper,long k){
        long cnt=0;
        int l=0;
        Map<Integer,Integer> freq=new HashMap<>();
        for(int r=0;r<nums.length;r++){
            freq.merge(nums[r],1,Integer::sum);// 移入右端点
            while(freq.size()>upper){// 窗口内元素过多
                int out=nums[l++];
                if(freq.merge(out,-1,Integer::sum)==0){
                    freq.remove(out);
                }
            }
            cnt+=r-l+1;// 右端点固定为r时，有r-l+1个合法左端点
            if(cnt>=k){
                return true;
            }
        }
        return false;
    }
}
